The present invention relates to the Connection Admission Control (CAC) finctions in a broadband Integrated Service Digital Network (TSDN) using cell/packet-based technologies of, either Asynchronous Transfer Mode (ATM) switch designs for both satellite and terrestrial applications, or new Internet Protocol (IP) router designs with Grade or Service (GoS) concepts such as differentiated service or Multi-Protocol Label Switching (MPLS) architectures.
New generations of broadband ISDN technologies that integrate many of the communications services required by the user (i.e., voice, data, moving images, etc.) have recently emerged in communications networks. Information from a large number of calls is transported via fixed-sized packets (or cells in ATM terminology) and then multiplexed onto a single medium whose capacity (in bits per second) is either expressed in a physical size (i.e, link capacity) or a virtual quantity (i.e. effective bandwidth allocation). At connection set-up, the user declares a set of traffic parameters and a required Quality of Service (QoS) from which the carrier must decide whether or not it is possible to establish a path of sufficient bandwidth between the sender and receiver that will satisfactorily accommodate the user""s requirement, Connection Admission Control (CAC) is the traffic control function within the network that performs this decision CAC typically depends on a resource allocation algorithm that determines if there are sufficient network resources (including bandwidth and buffer memory) throughout the communication path. In the event of insufficient resources the connection is denied.
Several prior art CAC models have been developed for determining solutions to the effective bandwidth (or effective cell rate) in large network traffic, however the software implementation of these algorithms has generally been too complicated to meet the real-time requirement for the bandwidth solution and the CAC xe2x80x9cgo/no-goxe2x80x9d decision. In order to reduce computation time, many network designers have resorted to simplified approximations such as the xe2x80x9con-offxe2x80x9d fluid flow approximation used in U.S. Pat. Nos. 5,862,126 and 5,917,804 (Shah et al, Jan. 19, 1999 and Jun. 29, 1999). Others have chosen empirical models such as the fuzzy logic decisions used in U.S. Pat. No. 5,341,366 (Soumiya et al, Aug. 23, 1994), and the methods for controlling priority levels in both U.S. Pat. No. 5,267,232 (Katsube et al, Nov. 30, 1992), and Canadian Patent Application No. 2,208,096 (M. Aida, Dec. 18, 1997). The bandwidth solutions developed in all of the known prior art CAC models, whether complex solutions or simplified approximations, are implemented in software only.
Other prior art schemes are described in references [1] to [7] listed at the end of this section. All such schemes are relatively complex in one or more of the following aspects
(a) Computation Speed
The CAC algorithms described in references [1], [3] and [5] are too complicated for real-time applications, such as: Terabit switch/router designs or Low Earth Orbiting satellite access/switching applications, where a relatively large amount of connections need to be processed or handed-off within a few seconds. In such real-time applications, a faster low-level CAC method that would be more suitable for hardware implementation is desirable.
(b) Robustness
When the network is down for some reason, the CAC solutions described in references [1], [3] and [5] may not offer sufficient robustness to recover the same connection on a link due to their complicated method for calculating the effective cell rate (ECR).
(c) Flexibility
As the Internet market grows, major carriers are paying more and more attention to fractal (self-similar) traffic, in addition to the non-self-similar traffic. References [1] and [5] describe a CAC implementation for non-self-similar cases only. Reference [3] describes a case for a self-similar application, however, neither this reference nor any other known report has described the implementation of self-similar cases. Given that data and video traffics are self-similar in nature, as shown in reference [3], and that these traffics are expanding at a considerable pace, there is clearly a need for a CAC implementation that handles both self-similar and non-self-similar traffic at the same time.
(d) Reliability
Careless (or malicious) users may, inadvertently or deliberately, provide a set of traffic parameter values that could render a complicated CAC algorithms invalid, possibly causing the processor performing the computation to crash. In this respect, the complexity of the CAC solutions as described in references [1], [3] and [5] may not permit the system to be sufficiently reliable for mission-critical applications such as telebanking and telemedicine.
(e) Accuracy
The Average Burst Size (ABS) is a traffic parameter that neither the ATM Forum Specifications described in reference [4], nor other known prior art CAC solutions have taken into account. Conventional CAC methods assume that the ABS and the Maximum Burst Size (MBS) are relatively the same, which is not accurate. As a result of this assumption, present CAC solutions based solely on the input descriptor MBS tend to over-estimate the effective bandwidth, leading to low bandwidth and buffer efficiency. It is desirable to have a CAC implementation that takes both ABS and MBS into account to more effectively remedy this problem.
(f) Automation
Existing CAC solutions such as those described in references [1] and [5] rely on complementary manual tuning of the CAC formula by a trained network operator. This manual operation is not a cost-effective approach to network management. It is therefore desirable to have a more cost-effective self-tuned CAC implementation.
[1] Harry G. Perros and Khaled M. Elsayed, xe2x80x9cCall Admission Control Schemes: A Review,xe2x80x9d IEEE Communications Magazine, November 1996.
[2] Mehrvar, H. R. and Le-Ngoc, T., xe2x80x9cEstimation of Degree of Self-Similarity for Traffic Control in Broadband Satellite Communications,xe2x80x9d CCECE""95, Montreal, September 5-8, (1995).
[3] I. Norros, xe2x80x9cOn the use of Fractional Brownian Motion in the Theory of Connectionless Networks,xe2x80x9d JSAC, Vol. 13, No. 6, 1995, pp. 953-962.
[4] ATM Forum, UNI3.0 Specification, 1993.
[5] R. J. Gibbens and P. J. Hunt, xe2x80x9cEffective Bandwidths for the Multi-type UAS. Channelsxe2x80x9d Queueing Systems 9, 1991, pp. 17-28.
[6] A. G. Greeberg, R. Srikant, W. Whitt, xe2x80x9cResource Sharing for Book-Ahead and Instantaneous-Request Callsxe2x80x9d IEEE/ACM Trans. On Networking, pp. 10-pp22, February, 1999.
[7] Y. Chen, Z. Deng, and C. L. Williamson, xe2x80x9cA Model for Self-Similar Ethernet LAN Traffic: Design, Implementation and Performance Implementationsxe2x80x9d, University of Saskatchewan, Dept. of Computer Science, working paper, 1997.
It is an object of the present invention to provide an improved apparatus and method for Connection Admission Control (CAC) solution, that solves the self-similar implementation problem in order to satisfy both fractal (self-similar) and non-self-similar traffic requirements in emerging broadband ISDN networks, such as virtual satellite networks and new internet protocol designs.
It is another object of the invention to simplify and reduce the mathematical calculations of the CAC solution, thereby minimizing the computational time to allow for a real-time implementation.
It is a further object of the invention to provide a minimum hardware implementation of the CAC solution that uses logarithmic operations in a pure additive/subtractive process to speed up the CAC computation at a real-time rate unmatched by traditional software approaches.
It is another object of the invention to provide a hardware implementation that permits the recovery of traffic connection in case of a link failure.
It is another object of the invention to detect, measure and calculate the Average Burst Size (ABS) and the Hurst value for each applicable service class in order to avoid over-estimation (which wastes system resources) or under-estimation (which jeopardizes the system performance).
It is a further object of the invention to provide automated measurements when deriving the CAC solutions in order to resolve the inefficiencies associated with manual operation.
To achieve the above objectives of the present invention, there is provided a cell or packet-based CAC method and apparatus for calculating the effective bandwidth in large network traffic that uses either ATM switches for both satellite and terrestrial applications or new Internal Protocol (IP) router designs with GoS concepts such as differentiated services or Multi-Protocol Label Switching (MPLS) architecture. The invention provides a real-time hardware implementation of CAC that satisfies the complex Effective Bandwidth equations for both self-similar and non-self-similar traffics. The invention provides a minimum hardware implementation that uses logarithmic principles in a pure additive formula to speed up the complex CAC computation and provide near real-time solutions that are unmatched by traditional software designs.
In accordance with an aspect of the present invention there is provided a system for Call Admission Control (CAC) within a data network for a new call having a class of service, said system comprising:
a) means for periodically obtaining from said data network data flow information and a set of parameter values corresponding to a set of network resource parameters;
b) a Hurst meter block for determining Hurst parameter (H) value from the data flow information based on the class of service;
c) a TF block for determining a Tuning Factor (TF) value from the data flow information;
d) an ECR calculator block responsive to the Hurst meter block and the TF block for determining an Effective Cell Rate (ECR) value;
e) an accumulator block responsive to the ECR calculator block for estimating required Total Effective Cell Rate (TECR) value;
f) a BF block for determining a Reference Effective Cell Rate (RECR) value from the data flow information and the set of parameter values; and
g) a comparator block responsive to the accumulator block and the BF block for comparing the values of TECR and RECR and providing a go-no-go sign indicating that the new call is to be accepted when TECR less than RECR, and that the new call is to be rejected otherwise;
wherein the value of TECR is updated within the accumulator block when the new call is accepted.
The set of network resource parameters includes buffer size (BS), peak cell rate (PCR), sustainable cell rate (SCR), and user specified Cell Loss Ratio (CLRs) corresponding to the class of service.
In an embodiment of the present invention, the ECR calculator block determines the ECR value by first extracting a Maximum Burst Size (MBS) value from the data flow information, and then using the formula of:
ECR=SCR/[CLRs (SCPR/PCR)]MBS/(BS/TF)/(2xe2x88x922H)
To perform the calculations for this formula, the ECR calculator block includes a hardware circuit having a multiplier, an exponentiator and a plurality of dividers for calculating the ECR value.
In a preferred embodiment, the ECR calculator block calculates the ECR value by first extracting a Maximum Burst Size (MBS) value from the data flow information, and then using the formula of:
Log ECR=Log SCRxe2x88x92[Log CLR+Log SCRxe2x88x92Log PCR]xc3x97Exponent
where Exponent=[MBS/(BS/TF)]/(2xe2x88x922H).
To perform the calculations for this formula, the ECR calculator block includes a hardware circuit having a plurality of subtractors, adders, log tables, and an anti-log table calculating the ECR value in a plurality of logarithmic operations. At least one of the plurality of log tables is preceded by a multiplexer and succeeded by a demultiplexer to permit sharing of said table among a plurality of logarithmic operations.
In yet another embodiment, the set of resource parameters includes link capacity (LC) and user specified Cell Loss Ratio (CLRs), and wherein the BF block determines the RECR value by setting a booking factor (BF) value, and calculating RECR as LC/BF. The BF block derives from the data flow information a measured Cell Loss Ratio (CLRm) value by dividing the number of discarded cells over the number of transferred cells, and then compares the values of CLRm and CLRs, such that the BF value is decreased when CLRm less than CLRs, and increased when CLRm greater than CLRs. The BF block sets a predetermined upper bound for the BF value such that when the BF value reaches the upper bound, an incremental increase in buffer threshold is effected for said class of service. In this same embodiment, the T7 block determines the TF value by deriving an Average Burst Size (ABS) value and extracting a Maximum Burst Size (MBS) value from the data flow information based on the class of service, and then calculating the TF value as ABS/MBS for each applicable class of service The Hurst meter block sets the value of H to 0.5 for non-self similar traffic. The accumulator block estimates the TECR value by keeping track of calls released and calls to be accepted by the data network.
In another embodiment, the CAC system further comprising an ECR recovery block for updating the TECR value within the accumulator block upon recovery from an interrupted connection.
In another aspect of the present invention, there is provides a method of Call Admission Control (CAC) within a data network for a new call having a class of service, said method comprising the steps of:
a) periodically obtaining from said, data network data flow information and a set of network parameter values corresponding to a set of resource parameters;
b) determining a Hurst parameter (T) value;
c) determining a Tuning Factor (TF) value,
d) determining an Effective Cell Rate (ECR) value;
e) estimating a required Total Effective Cell Rate (TECR) value;
f) determining a Reference Effective Cell Rate (RECR) value;
g) comparing the values of TECR and RECR such that the new call is to be accepted when TECR less than RECR, and the new call is to be rejected otherwise;
h) updating the value of TECR when the new call is accepted.
The set of network resource parameters includes buffer size (BS), peak cell rate (PCR), sustainable cell rate (SCR), and user specified Cell Loss Ratio (CLRs) corresponding to the class of service. The H value is determined from the class of service and data flow information. The ECR value is determined by using the H value, the TF value and said set of resource parameters.
In an embodiment of this invention, the step of determining the ECR value includes the steps of:
(i) exacting a Maximums Burst Size (MBS) value from the data flow information; and
(ii) calculating the ECR value by using the formula of:
ECR=SCR/[CLRs (SCR/PCR)]MBS/(BS/TF)/(2xe2x88x922H)
In another embodiment of this invention, the step of determining the ECR value includes the steps of:
(i) extracting a Maximum Burst Size (MBS) value from the data flow information; and
(ii) calculating the ECR value by using the formula of:
Log ECR=Log SCRxe2x88x92[Log CLR+Log SCRxe2x88x92Log SCR]xc3x97Exponent
where Exponent=[MBS/(BS/TF)]/(2xe2x88x922H).
In yet another embodiment of this invention, the set of resource parameters includes link capacity (LC) and user specified Cell Loss Ratio (CLRs), wherein the step of determining the RECR value includes the steps of:
(i) setting a booking factor (BF) value; and
(ii) calculating RECR as LC/BF.
The step of setting the BF value includes the steps of:
(i) deriving from the data flow information a measured Cell Loss Ratio (CLRm) value as the number of discarded cells over the number of transferred cells; and
(ii) comparing the values of CLRm and CLRs, such that the BF value is decreased when CLRm less than CLRs, and increased when CLRm greater than CLRs.
A predetermined upper bound is set for the BF value such that when the BF value reaches the upper bound, an incremental increase in buffer threshold is effected for said class of service.
The step of determining the TF value includes the steps of:
(i) deriving an Average Burst Size (ABS) value and extracting a Maximum Burst Size (MBS) value from the data flow information based on the class of service; and
(ii) calculating the TF value as ABS/MBS for each applicable class of service. The value of H is set to 0.5 for non-self similar traffic.
The step of estimating TECR is performed by keeping track of calls released and calls to be accepted by the data network. This TECR value is updated upon recovery from an interrupted connection.
Prior art methods for calculating the Effective Bandwidth (EB) are typically complicated, computationally difficult, and depend greatly on mathematical assumptions Yet, the operator in the field is still required to manually adjust the CAC to meet the real traffic situation as traffic profiles evolve, rendering the sophisticated calculations non-useful. The present invention overcomes this problem by offering a simple, xe2x80x9cback-to-basicsxe2x80x9d, self-tuned hardware CAC implementation that needs little or no manual in the field.
Advantages of the present invention over prior art include a considerable increase in computational speed, flexibility in implementing the complex formula for both self-similar and non-self-similar traffic, increased accuracy by taking both the ABS and MBS factors into account, increased reliability for mission-critical applications, robustness in recovering connection in case of a link failure, and a more cost-effective automated approach to resolving the inefficiencies associated with manual operation.
In a cell/packet based network, including ATM and IP networks for all service categories that transmit Data Units, each ATM switch or IP router must allocate enough bandwidth and buffer to guarantee that the required QoS for each virtual channel (or GoS for each flow) will be satisfied. As a preventive mechanism for network congestion, CAC is performed at connection (or flow) set-up time to determine if the new connection (or flow) can be accepted in terms of both its own service requirements and any impact it may have on already existing connections (or flows). Logically the xe2x80x9cgo/no-goxe2x80x9d decision of the CAC function must be performed for each statistical element of the network. For example, in satellite environments these elements include the transmitting queue in the ground terminal, the up-link ingress queue, the fabric queue, the down-link queue is in the on-board switch, and the receiving queue in the ground terminal. For each of these elements, a CAC engine can be implemented.
For convenience, a glossary of acronyms used in this description is given below.
ABR Available Bit Rate
ABS Average Burst Size
ATM Asynchronous Transfer Mode
BF Booking Factor
BFBS Buffer with Factor scaled Size
BS Buffer Size
CAC Connection Admission Control
CBR Continuous Bit Rate
CFI Cell (or data) Flow Information
CLR Cell Loss Ratio
CLRm Measured value of Cell Loss Ratio
CLRs User Specified Cell Loss Ratio
CoS Class of Service
EB Effective (or equivalent) Bandwidth
ECR Effective Cell Rate
GFR Guaranteed Frame Rate
GoS Grade of Service
H Hurst parameter
HST Hurst Smoothness of Traffic
IP Internet Protocol
LC Link Capacity
MBS Maximum Burst Size
MIB Management Information Base
PCR Peak Cell Rate
QoS Quality of Service
RECR Reference Effective Cell Rate
SCR Sustainable Cell Rate
TECR Total Effective Cell Rate
TF Tuning Factor
UBR Unspecified Bit Rate
VBR Variable Bit Rate